"""
https://leetcode.cn/problems/restore-ip-addresses/description/

93. 复原 IP 地址
中等
相关标签
相关企业
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

 

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：

输入：s = "0000"
输出：["0.0.0.0"]
示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
 

提示：

1 <= s.length <= 20
s 仅由数字组成

"""
from typing import List


class Solution:
    """
    涉及到复数个解的情况，不妨先用数学归纳的思想考虑。
    假定sp(s,n)表示对字符串s进行拆分为n个部分的结果集。
    则可对s的后n位进行分割。
    分隔的字符串规则符合：
    1. 1~3位字符串
    2. 如果是2位以上，则首位不能为0
    3. 转化为数字小于等于255
    以此规则逐步分割，最后分割后的字符串如果是""，则合格；否则ng

    """
    def restoreIpAddresses(self, s: str) -> List[str]:
        def is_ip_part(s:str)->bool:
            if len(s)==1:
                return True
            if len(s)==2:
                return s[0]!='0'
            if len(s)==3:
                return s[0]!='0' and int(s)<=255
            return False
        
        def sp(r:str,n:int)->List[List[str]]:
            if len(r)<n or len(r)>n*3:
                return []
            if n==1:
                if is_ip_part(r):
                    return [[r]]
                else:
                    return []
            res=[]
            for i in range(1,min(3,len(r))+1):
                # 1,2,3
                left_str=r[:i]
                if not is_ip_part(left_str):
                    continue
                right_str=r[i:]
                right_arr=sp(right_str,n-1)
                for each_arr in right_arr:
                    start_arr=[left_str]
                    start_arr.extend(each_arr)
                    res.append(start_arr)
            return res

        res_arr=sp(s,4)
        return ['.'.join(_) for _ in res_arr]   
            
        pass

if __name__ =='__main__':
    s='0000'

    sol=Solution()
    res=sol.restoreIpAddresses(s)
    print(res)